The present invention is related to a method and apparatus for switching cells with a scheduler as a function of a memory mechanism""s occupancy. More specifically, the present invention is related to an ATM switch which stamps explict rate to ABR VCs for controlling ABR traffic flow on a given link of the ATM switch with a scheduler as a function of a memory mechanism""s occupancy.
The Available Bit Rate (ABR) service of ATM networks was defined for bursty data applications which can adapt to time-varying bandwidth but which require low cell loss rate [ATM Forum. Traffic management specification version 4.0, April 1996]. ABR virtual connections (VCs) share the available bandwidth fairly, where the available bandwidth is the bandwidth leftover by the constant bit rate (CBR) and variable bit rate (VBR) traffic streams. In addition to getting a fair share of the available bandwidth, an ABR VC can also specify a minimum cell rate (MCR) which, once the ABR VC is admitted, is guaranteed.
The network provides the ABR sources with feedback information regarding the available bandwidth. Two feedback control approaches were studied: In the credit-based approach, a network node sends per-VC credits to the upstream node and the upstream node uses up a credit when it transmits a cell belonging to the VC. In the rate-based approach, the source periodically sends Resource Management (RM) cells which are turned back by the destination. The switches along the VC route indicate their congestion status in the returning RM cell.
Although, the credit-based approach (see e.g., [H. Kung and R. Morris. Credit-based flow control for ATM networks. IEEE Networks, 9 (2):40-48, March/April 1995]) is conceptually simpler and guarantees zero cell losses, the ATM Forum selected the rate-based approach (see e.g., [F. Bonomi and K. Fendick. The rate-based flow control framework for the available bit rate ATM service. IEEE Networks, 9(2):25-39, March/April 1995]) because it offered greater architectural flexibility. The complexity of the switch algorithm under the rate-based approach can be as simple as marking a congestion bit to as complex as computing an explicit rate (ER).
The ATM Forum defined the behavior of the end systems but left the details of the ABR switch algorithm design to the ATM switch designers. Several ER computing switch algorithms have been proposed and they essentially fall into two categories: exact fair share and approximate fair share computing algorithms. An exact fair share computing algorithm such as ERICA, ERICA+ [R. Jain, S. Kalyanaraman, R. Goyal, Fahmy S., and R. Viswanathan. ERICA switch algorithm: A complete description. ATM Forum Document Number: ATM Forum/96-1172, August 1996] and EDERA [N. Ghani. Available Bit Rate Service in ATM Networks. PhD thesis, University of Waterloo, 1997] measures the net available bandwidth of the switch output port and the number of active ABR VCs passing through the port. It then computes the fair share by dividing the available bandwidth by the number of active ABR VCs. On the other hand, an approximate fair share computing algorithm sch as the PRCA and EPRCA [L. Roberts. Enhanced PRCA (proportinal rate-control algorithm). ATM Forum Document: AF-TM 94-0735R1, August 1994], DMRCA and EDMRCA [F. M. Chiussi and Y. T. Wang. An ABR rate-based congestion control algorithm for ATM switches with per-VC queueing. In GLOBECOM ""97, pages 771-778, 1997] avoids the floating-point division operation. It maintains port variables which are adjusted according to the congestion status of the switch output port. The ER of each VC is determined from these port variables. In general, the exact fair share computing algorithms perform better than the approximate fair share computing algorithms [N. Ghani. Available Bit Rate Service in ATM Networks. PhD thesis, University of Waterloo, 1997].
An important problem associated with the exact fair-share computing approach is the redistribution of bandwidth from ABR VCs bottle-necked elsewhere to those bottle-necked at the switch. For example, consider three active ABR VCs each with zero MCR, and let the net available bandwidth be 30 Mbits/sec, then the fair share for each ABR VC is 10 Mbits/sec. Assume that the first two ABR VCs are bottle-necked at the switch whereas the third ABR VC is bottle-necked at some other switch which prevents the third ABR VC from using more than 5 Mbits/sec. This implies that a bandwidth of 30xe2x88x92(10+10+5)=5 Mbits/sec has to be redistributed among the first two ABR VCs. Thus, the fair shares for the three VCs should be 12.5, 12.5, and 5.0 Mbits/sec, respectively.
The Explicit Rate Indication for Congestion Avoidance (ERICA), and ERICA+ [R. Jain, S. Kalyanaraman, R. Goyal, Fahmy S., and R. Viswanathan. Determining the number of active ABR sources in switch algorithms. ATM Form Document Number: ATM Forum/98-0154, February 1998; R. Jain, S. Kalyanaraman, R. Goyal, Fahmy S., and R. Viswanathan. ERICA switch algorithm: A complete description. ATM Form Document Number: ATM Forum/96-1172, August 1996] employ complex schemes for the redistribution which require the measurement of per-VC service rates. For example, ERICA+ solves the redistribution problem by dividing the available bandwidth by the effective number of active ABR VCs, rather than by the number of active ABR VCs. The effective number of active ABR VCs is defined as follows: The ABR VCs which are bottle-necked at the switch are counted as one whereas those which are bottle-necked elsewhere are counted only as a fraction equal to (Actual VC rate/Fair Share). Thus, to compute the effective number of active ABR VCs, the cell rate of each VC has to be measured at the switch port. The measurements of VC rate entails algorithms with O(n) space compleity and/or O(n) time complexity, where n is the number of VCs passing through the port. Hence, such switch algorithms are very expensive to implement in high-speed hardware.
The Enhanced Distributed Explicit Rate Algorithm (EDERA) [N. Ghani. Available Bit Rate Service in ATM Networks. PhD thesis, University of Waterloo, 1997] solves the redistribution problem by explicitly keeping track of the ABR VCs which are bottle-necked at the switch versus those bottle-necked elsewhere. EDERA assumes that the ABR sources indicate their segmented average source rate (SASR) in the RM cells where SASR is defined as the ratio of number of data cells between two RM cells to the time between the two RM cells. Note that SASR will be less than Allowed Cell Rate (ACR) if the VC is bottle-necked at some point in the network. Since the ATM Forum standards [ATM Forum. Traffic management specification version 4.0, April 1996] have opted not to include SASR indications in the RM cells, the EDERA scheme has to be suitably modified. Such a modification entails the measurement of VC rates at the switch output ports.
The present invention is directed to a novel ABR switch algorithm, Simple Explicit Rate Indication Algorithm (SERIA). Unlike ERICA, ERICA+ and EDERA, SERIA does not need to measure per-VC rates. In fact, SERIA is much simpler than the previously proposed exact fair share computing switch algorithms: The number of arithmetic and logical operations needed to handle events such as cell arrival and cell departure is a small number independent of the number of VCs. The simplicity of SERIA makes it particularly attractive for high speed implementations [M. Vishnu, D. Basak, and H. S. Kim. Method and apparatus for a simple explicit rate indication algorithm (SERIA) U.S. Patent Pending, 1998].
Extensive simulation results show that SERIA provides max-min fairness, converges to steady state quickly, utilizes 100% of the link bandwidth, and maintains tight buffer control.
The present invention pertains to an apparatus for switching cells from entities in a network. The apparatus comprises an input mechanism for receiving all cells by the apparatus from the network. The apparatus comprises a memory mechanism for storing all cells received by the input mechanism that are to be stored in the apparatus. The memory mechanism is connected to the input port mechanism. The memory mechanism has an occupancy for cells. The apparatus comprises an output mechanism for sending cells from the apparatus to the network. The apparatus comprises a server for providing service to the cells at a service rate. The server is connected to the memory mechanism and the output mechanism. The apparatus comprises a scheduler for providing service to the cells in the memory mechanism. The scheduler is connected to the server and the memory mechanism.
The present invention pertains to a method for switching cells. The method comprises the steps of receiving cells of J entities, where J is greater than or equal to 1, from a network at an input mechanism of a switch. Then there is the step of storing the cells in the memory mechanism of the switch. Next there is the step of providing service to the cells in the memory mechanism by a server. Then there is the step of scheduling with a scheduler of the switch when cells in the memory mechanism are to receive service from a server of the switch as a function of the occupancy of the memory mechanism by cells.
The present invention pertains to an ATM switch which stamps Explicit Rate to ABR VCs for controlling ABR traffic flow on a given link of the ATM switch. The apparatus comprises input port mechanisms carrying traffic for VCs into the switch. The apparatus comprises a memory mechanism for storing all cells of VCs received by the input port mechanisms that are to be stored in the switch. The memory mechanism is connected to the input port mechanisms. The memory mechanism has an occupancy for cells of VCs. The apparatus comprises output port mechanisms for sending cells from the switch to the network. The apparatus comprises a switching fabric to switch a cell of a VC from an input port mechanism to an output port mechanism. The apparatus comprises a ABR-ER mechanism for computing explicit rate (ER) and stamping rate on backward RM cells. The apparatus comprises a server for providing service to the cells of VCs at a service rate. The server is connected to the memory mechanism and the output port mechanisms. The apparatus comprises a scheduler for providing service to the cells of the VCs as a function of the memory mechanism""s occupancy by the cells of the VCs, and the scheduler is connected to the server and the memory mechanism.